package zcw.com.lib_leet_code;

import zcw.com.lib_leet_code.bean.ListNode;
import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/8/17.<br><br>
 *
 * 中等：删除链表的倒数第 N 个结点
 */
public class Topic19 {

    public static void main(String[] args) {
        Topic19 instance = new Topic19();

        int[] array = new int[] {1,2,3,4,5};
        ListNode head = Util.createList(array);
        Util.printList(instance.removeNthFromEnd(head, 2));

        array = new int[] {1};
        head = Util.createList(array);
        Util.printList(instance.removeNthFromEnd(head, 1));

        array = new int[] {1,2};
        head = Util.createList(array);
        Util.printList(instance.removeNthFromEnd(head, 1));
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode start = new ListNode(0);

        ListNode low = start;
        ListNode fast = start;
        low.next = head;

        for(int i = 0; i <= n; i++) {
            fast = fast.next;
        }

        while (fast != null) {
            low = low.next;
            fast = fast.next;
        }

        low.next = low.next.next;
        return start.next;
    }
}
